#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/11 21:17
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _113_pathSum.py
from copy import deepcopy


class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.dfs(root, targetSum, path, res)
        return res

    def dfs(self, node, target, path, res):
        if node == None:
            return

        curr_target = target - node.val
        path.append(node.val)
        if node.left == None and node.right==None:
            if curr_target==0:
                res.append(deepcopy(path))
        self.dfs(node.left, curr_target, path, res)
        self.dfs(node.right, curr_target, path,res)

        path.pop(len(path)-1)